/* Heapsort.
   1. First convert the array into a binary heap. Each node is greater than
      its children. The biggest element is now at the root.
   2. Swap root with the last element. i.e. The biggest is in it's place.
   3. Sift the element at the root (now not the biggest) down until the heap is
      formed again.
   4. Do steps 2-3 until heap size is 1 */
#include <stdio.h>

void swap(int *x, int *y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

void print_arr(int arr[], int n)
{
	int i = 0;

	for (i = 1; i<=n; i++)
		printf("%4d ", arr[i]);

	printf("\n");
}


/* sift_down ensures the heap property applies at the final position of a value
 * that was at start in the beginning. It moves it down the heap until true
 */
void sift_down(int arr[], int start, int end)
{
	int cur = start;
	int child;

	while (cur <= end / 2) {
		child = cur * 2;
		if ((child < end) && arr[child + 1] > arr[child])
			child = child + 1;

		if (arr[cur] < arr[child]) {
			swap(&arr[cur], &arr[child]);
			cur = child;
		} else {
			break;
		}
	}
}

void heapify(int arr[], int n)
{
	int i;

	for ( i = n / 2; i >= 1; i--)
		sift_down(arr, i, n);
}

void heap_sort(int arr[], int n)
{
	int end = n;
	heapify(arr, n);
	printf("Init heap: ");
	print_arr(arr, n);

	while (end > 1) {
		printf("swap %4d: ", arr[1]);
		swap(&arr[1], &arr[end]);
		print_arr(arr, n);

		/* The element at the root is probably not the biggest now.
		 * Sift it down to not violate the heap */
		printf("sift   %2d: ", arr[1]);
		sift_down(arr, 1, --end);
		print_arr(arr, n);
	}
}

int main(void)
{
	int arr[] = {9999, 22, 13, 43, 67, 7, 4, 15, 81, 46, 64, 8, 17, 18, 93};
	int size = sizeof(arr)/sizeof(arr[0]);

	heap_sort(arr, size - 1);

	return 0;
}

